{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# TP8 (Mini-Projet) : Promenons-Nous dans des Graphes...\n", "\n", "Internet peut être considéré comme un grand graphe, dans lequel les sommets sont les sites internet, et les arêtes l'existent d'un lien sur un site, pointant vers un autre site.\n", "Ainsi, par exemple, sur le [site de l'université de Lille](https://www.univ-lille.fr/), il y a des liens vers Facebook, Twitter, Instagram et Youtube.\n", "Il y a donc des liens entre le site de l'université de Lille et chacun de ces quatre autres sites.\n", "\n", "Un problème majeur dans cette jungle de sites internet est d'essayer de s'y repérer.\n", "C'est une tâche particulièrement difficile car d'une part, on ne connaît pas forcément tout le graphe, ne pouvant accéder qu'aux pages que l'on connaît, mais surtout, d'autre part, parce que ce graphe est extrêmement grand.\n", "\n", "Les moteurs de recherche permettent de trouver son chemin dans ce graphe : ils effectuent une sélection des sites pertinents selon une recherche par mots clés, puis les renvoient, par exemple, dans leur ordre d'importance.\n", "\n", "Cela signifie que l'on a besoin d'attribuer à chacun des sites d'Internet une valeur, qui détermine son importance sur Internet.\n", "L'intuition qui a mené à la fondation de Google est qu'un site est important si :\n", "* beaucoup de sites pointent vers ce site ;\n", "* ces sites sont eux-mêmes importants.\n", "\n", "C'est sur ce principe que se base la notion de PageRank, qui attribue un score entre $0$ et $1$ à chacun des sites d'Internet.\n", "\n", "Ce problème se situe à la frontière entre les graphes et le machine learning.\n", "En fait, c'est un problème d'apprentissage non-supervisé, comme on va le voir la semaine prochaine en cours : on cherche à donner une structure à un ensemble de valeurs, mais on ne connaît pas cette structure *a priori*.\n", "Ici, on cherche à déterminer quels sont les sites les plus importants sur Internet, mais on n'a aucune connaissance *a priori* de l'importance de ces sites.\n", "\n", "Le TP se divise en trois grandes parties :\n", "* d'abord, on étudie les marches aléatoires sur un exemple. On commence par définir ce que sont les marches aléatoires, puis on regarde sur deux exemples où nos marcheurs finissent ;\n", "* ensuite, on va faire le lien avec ce qu'on a déjà vu sur les graphes, en représentant ce problème sous une forme matricielle, qui va s'avérer fort utile ;\n", "* finalement, on va modifier un petit peu cette matrice de façon à contourner les cas problématiques que l'on a vus en exemple dans la première partie, puis on l'utilisera pour calculer ce fameux PageRank.\n", "\n", "Ce TP est à rendre pour le **16 avril 2021** sur Moodle.\n", "\n", "Vous pouvez faire ce TP par binômes (ou seul-e), à la seule condition de me prévenir avant **vendredi prochain (2 avril)** si vous décidez de former un binôme.\n", "\n", "\n", "## Marche Aléatoires dans un Graphe" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import networkx as nx\n", "import numpy as np\n", "import pandas as pd\n", "import matplotlib.pyplot as plt" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Commençons par un petit exemple.\n", "Ici, on se promène sur internet dans un ensemble de sites assez restreint.\n", "On se promène de la façon suivante : quand on est sur un site donné, on peut cliquer sur les liens qui s'y trouvent, et c'est tout.\n", "\n", "Prenons l'ensemble de sites très restreint suivant.\n", "On attribue à chaque site un identifiant unique (id), et on garde en mémoire son adresse (url) et les liens qu'il contient (links)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "websites = {\n", " \"id\": [0,1,2,3],\n", " \"url\": [\"univ-lille.fr\", \"wikipedia.fr\", \"arxiv.org\", \"youtube.com\"],\n", " \"links\": [[1],[2,3],[0,1,3],[]]\n", "}\n", "\n", "web = pd.DataFrame(data=websites)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La librairie `pandas` permet de regarder et d'utiliser de façon très simple ce type de jeux de données.\n", "Regardons notre petite base de données :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "web" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 1.** Ces sites internet forment un ensemble de points, avec un ensemble de liens. Cela définit donc un graphe où les sommets sont les sites, et les arêtes les liens entre les sites.\n", "Sous quelle forme est donné ce graphe dans la variable `web` ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Réponse :*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut afficher ce graphe avec la libraire `networkx`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# graphe orienté\n", "G_web = nx.DiGraph()\n", "\n", "# on ajoute les arêtes au graphe\n", "edges = [(i, link) for i, site_links in enumerate(websites[\"links\"]) for link in site_links ]\n", "G_web.add_edges_from(edges)\n", "\n", "# urls des sites à afficher sur le graphe\n", "labels = {i: u for i, u in enumerate(web[\"url\"])}\n", "\n", "# affichage du graphe\n", "pos = nx.spring_layout(G_web, seed=42)\n", "nx.draw(G_web, pos, node_color=\"pink\", edgecolors=\"black\", node_size=500)\n", "nx.draw_networkx_labels(G_web, pos, labels, font_size=10, font_color='black');" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Supposons que l'on se promène sur ce graphe en partant de *univ-lille.fr*, et en cliquant sur les liens que l'on rencontre. Quand il y a plusieurs liens sur un site, on choisit uniformément aléatoirement celui sur lequel on clique.\n", "\n", "Ainsi, si l'on est sur `wikipedia.fr` on a une chance sur deux d'aller sur `youtube.com` et une chance sur deux d'aller sur `arxiv.org`.\n", "Cela définit ce que l'on appelle une **marche aléatoire** : c'est le trajet emprunté par un petit personnage qui se promènerait sur notre graphe et qui choisirait au hasard la direction qu'il prend à chaque fois qu'il rencontre un embranchement (ie. un sommet du graphe).\n", "\n", "C'est un objet très étudié en mathématiques, et qui a de nombreuses applications.\n", "On peut par exemple montrer qu'un petit personnage se baladant au hasard sur une grille infinie en deux dimensions, par exemple dans les rues d'une ville (infinie, certes...), finira presque sûrement par repasser par son point de départ." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 2.** Mais revenons à notre graphe. Sur quel site finirait un petit personnage qui part du site *univ-lille.fr* et qui se promène aléatoirement sur ce graphe (pendant suffisamment longtemps) ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Réponse :*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On va vérifier cette conjecture numériquement.\n", "Pour cela, on va avoir besoin d'une fonction qui permet de se déplacer dans notre graphe.\n", "\n", "**Question 3.a.** Commencez par afficher le contenu de la variable `websites[\"links\"]`.\n", "Que représente `websites[\"links\"][0]` ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Réponse :*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 3.b.** Implémentez une fonction qui simule la marche aléatoire de notre personnage dans notre graphe. Cette fonction prendra en argument une liste d'adjacence, une position initiale (sous la forme d'un entier) et le nombre de déplacements du personnage.\n", "\n", "Ainsi, au début, le personnage est sur le sommet `sommet_initial`, puis on tire uniformément aléatoirement un sommet dans ses voisins.\n", "Pour effectuer ce tirage, on pourra utiliser la fonction `np.random.choice`, en faisant bien attention à traiter à part le cas où la liste des voisins du sommet courant est vide.\n", "\n", "Ensuite, il ne reste plus qu'à répéter cette opération `nb_deplacements` fois, puis à renvoyer le sommet courant." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def sommet_final(links, sommet_init, nb_deplacements):\n", " # ~~~ implémentez la fonction ~~~" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 3.c.** Lancez votre fonction avec la liste d'adjacence `websites[\"links\"]`, en partant du sommet *0*, pour un nombre de déplacement de *2* et pour un nombre de déplacements de *10*.\n", "\n", "Retrouvez-vous bien votre réponse à la question 2 ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Réponse :*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 4.a.** Créez une nouvelle base de données `websites2`, basée sur `websites`, à laquelle vous aurez rajouté un lien entre les sites *youtube.com* et *univ-lille.fr*, de façon à ce qu'un petit personnage se promenant aléatoirement sur ces pages web ne finisse pas bloqué sur un site donné." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Affichons le graphe correspondant :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# graphe orienté\n", "G_web2 = nx.DiGraph()\n", "\n", "# on ajoute les arêtes au graphe\n", "edges = [(i, link) for i, site_links in enumerate(websites2[\"links\"]) for link in site_links ]\n", "G_web2.add_edges_from(edges)\n", "\n", "# urls des sites à afficher sur le graphe\n", "labels = {i: u for i, u in enumerate(websites2[\"url\"])}\n", "\n", "# affichage du graphe\n", "pos = nx.spring_layout(G_web2, seed=42)\n", "nx.draw(G_web2, pos, node_color=\"pink\", edgecolors=\"black\", node_size=500)\n", "nx.draw_networkx_labels(G_web2,pos,labels,font_size=10, font_color='black');" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On se demande quelle est la probabilité de se retrouver sur chacun des sites si l'on effectue 100 déplacements à partir du sommet *0*. \n", "\n", "**Question 4.b.** Estimez numériquement ces probabilités en lançant mille fois la fonction `sommet_final` avec la liste d'adjacence définie à la question *4.a.*, en partant du sommet *0* et en effectuant *100* déplacaments. Vous pourrez par exemple stocker dans un tableau le nombre de fois que la fonction a renvoyé *0, 1, 2* ou *3* puis diviser par 1000 les nombres obtenus." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 4.c** Que constatez-vous ? Selon ce résultat, est-ce qu'un site semble être avoir plus d'importance que les autres ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Réponse :*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Représentation Matricielle\n", "\n", "En fait, si l'on regarde bien ce qu'il se passe ici, on est en train de chercher des chemins entre un point initial et les autres points de notre graphe.\n", "En revanche, contrairement à ce que l'on a vu en cours, ici on choisit uniformément aléatoirement le sommet vers lequel on va.\n", "\n", "On peut donc définir une matrice dont le coefficient $(i, j)$ est la probabilité de passer du sommet $i$ au sommet $j$.\n", "La matrice correspondant au graphe défini à la question 4.a. est donc maintenant la suivante :\n", "\n", "$$\n", "M = \\begin{pmatrix}\n", "0 & 1 & 0 & 0 \\\\\n", "0 & 0 & 1/2 & 1/2 \\\\\n", "1/3 & 1/3 & 0 & 1/3 \\\\\n", "1 & 0 & 0 & 0\n", "\\end{pmatrix}\n", "$$\n", "\n", "**Question 5.a.** Implémentez une fonction `matrice` qui prend en argument la liste des liens entre les sites, et qui renvoie la matrice définie ci-dessus." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def matrice(links):\n", " # ~~~ implémentez la fonction ~~~" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 5.b.** Calculer cette matrice pour la base de données `website2` de la question 4.a. (en donnant à `matrice` l'argument `website2[\"links\"]`) et vérifier que la matrice obtenue est bien la matrice $M$ ci-dessus." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La matrice ci-dessus ressemble à une matrice d'adjacence, dont les lignes ont été normalisées de façon à ce que la somme des coefficients des lignes soit égale à *1*.\n", "Ainsi, chaque ligne représente bien une loi de probabilité, dont chaque élément indique la probabilité d'arriver à un autre sommet en partant d'un sommet donné.\n", "\n", "Comme pour la matrice d'adjacence, on peut avoir envie de calculer les puissances de cette matrice.\n", "\n", "**Question 5.c.** Que représentent les puissances de cette matrice ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Réponse :*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut représenter la position de notre petit personnage par un vecteur, par exemple s'il est en position $0$, on représentera sa position par un vecteur dont la longueur est le nombre de sites et qui ne contient que des $0$ sauf dans son premier coefficients qui vaut $1$.\n", "\n", "Par exemple, dans le graphe ci-dessus, si le personnage est sur le site $0$, sa position sera représentée par le vecteur $[1,0,0,0]$.\n", "\n", "**Question 5.d.** Calculer la valeur de $(M^T)^K v$ où $M^T$ est la matrice transposée de la matrice $M$ ci-dessus et $v$ le vecteur $[1, 0, 0, 0]$, pour $K=100$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "v = [1.0, 0.0, 0.0, 0.0]\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 5.e.** On remarque que, à la fluctuation liée aux tirages aléatoires réalisés en 4.b. près, on obtient le même résultat.\n", "Expliquez pourquoi." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Réponse :*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 6.a.** Reprenez la base de données `websites`, et calculez la matrice `M_0` qui lui correspond.\n", "Calculez ensuite $(M_0^T)^K v$ pour $K = 100$. Que constatez-vous ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Réponse :*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 6.b.** Le résultat obtenu ne nous convient pas vraiment, car dans l'exemple `websites`, on a vu que l'on finissait toujours sur le site *youtube.com*, on voudrait donc plutôt obtenir un vecteur de zéros, avec un $1$ à la position correspondant à *youtube.com*.\n", "\n", "Créez une base de données `websites3` où vous rajouterez un lien entre *youtube.com* et lui-même.\n", "Calculez $(M_3^T)^K v$ pour $K = 100$, où $M_3$ est la matrice correspondant à ce nouvel ensemble de liens." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 6.c.** Que constatez-vous ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Réponse :*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Éviter de se Retrouver Bloqué\n", "\n", "La partie précédente montre que, sous certaines conditions, calculer les puissances de la matrice $M$ définie ci-dessus permet de trouver la probabilité de finir sur un site donné, en partant d'un site donné.\n", "\n", "En fait, les valeurs obtenues à la question 5.d suggèrent que, dans certains cas, la suite des puissances $(M^K)$ de la matrice $M$ converge vers une certaine matrice.\n", "Chacun des coefficients $(i, j)$ de cette matrice représente la probabilité de finir sur le site $j$ en partant du site $i$, et en cliquant sur un nombre infini de liens.\n", "Pour calculer cette matrice limite vers laquelle $(M^K)$ converge, on se contentera ici de calculer $M^K$ pour $K$ suffisamment grand, par exemple $K=100$.\n", "\n", "Toutefois, comme vu dans la question 6, il est possible qu'un site ne pointe vers aucun autre site.\n", "Dans un tel cas, soit ce site fait disparaître notre petit personnage (car il ne peut plus cliquer nulle part), soit, comme à la question 6.b, ce site piège notre petit personnage, qui n'arrive plus à repartir du site.\n", "\n", "Pour éviter que cela arrive, on peut changer un petit peu le comportement de notre personnage cliqueur.\n", "Ainsi, au lieu de simplement cliquer sur les liens présents sur le site qu'il est actuellement en train de visiter, on suppose qu'il peut aussi décider de taper une url dans sa barre d'adresse, et donc tomber sur n'importe quel autre site.\n", "\n", "On suppose que, quand il tape une url dans sa barre d'adresse, notre personnage peut taper n'importe laquelle, et qu'il a autant de chances de taper l'une que l'autre.\n", "Cette idée est l'idée qui se cache derrière l'algorithme du PageRank, qui a rendu Google célèbre.\n", "Ce petit personnage, dans leur version de l'algorithme, s'appelle un \"surfeur aléatoire\", car il clique sur les liens mais rentre aussi des url aléatoires dans sa barre d'adresse." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Reprenons notre ensemble de sites `websites`.\n", "La matrice lui correspondant, ainsi que définie dans la partie suivante était celle-ci :\n", "\n", "$$\n", "M_0 = \\begin{pmatrix}\n", "0 & 1 & 0 & 0 \\\\\n", "0 & 0 & 1/2 & 1/2 \\\\\n", "1/3 & 1/3 & 0 & 1/3 \\\\\n", "0 & 0 & 0 & 0\n", "\\end{pmatrix}\n", "$$\n", "\n", "On va la modifier un peu.\n", "Prenons un coefficient $\\alpha \\in [0, 1]$, et définissons une nouvelle matrice ligne par ligne.\n", "\n", "Pour chaque ligne $M_i$ de $M$ :\n", "* si tous les coefficients de la ligne sont nuls, on remplace $M_i$ par une ligne où tous les coefficients valent $1/n$, où $n$ est le nombre de sites ;\n", "* sinon, on remplace $M_i$ par $\\alpha M_i + (1 - \\alpha) \\frac{\\textbf{u}}{n}$ où $\\textbf{u}$ est un vecteur de $1$.\n", "\n", "Pour la matrice $M_0$ ci-dessus, on définit donc une matrice $M_0^\\alpha$ qui vaut :\n", "\n", "$$\n", "M_0^\\alpha = \\begin{pmatrix}\n", "0 & \\alpha & 0 & 0 \\\\\n", "0 & 0 & \\alpha/2 & \\alpha/2 \\\\\n", "\\alpha/3 & \\alpha/3 & 0 & \\alpha/3 \\\\\n", "0 & 0 & 0 & 0\n", "\\end{pmatrix}\n", "+ \\begin{pmatrix}\n", "(1-\\alpha)/4 & (1-\\alpha)/4 & (1-\\alpha)/4 & (1-\\alpha)/4 \\\\\n", "(1-\\alpha) & (1-\\alpha) & (1-\\alpha) & (1-\\alpha) \\\\\n", "(1-\\alpha) & (1-\\alpha) & (1-\\alpha) & (1-\\alpha) \\\\\n", "1/4 & 1/4 & 1/4 & 1/4\n", "\\end{pmatrix}\n", "$$\n", "\n", "Et, par exemple, pour $\\alpha = 1$, on a :\n", "\n", "$$\n", "M_0^1 = \\begin{pmatrix}\n", "0 & 1 & 0 & 0 \\\\\n", "0 & 0 & 1/2 & 1/2 \\\\\n", "1/3 & 1/3 & 0 & 1/3 \\\\\n", "1/4 & 1/4 & 1/4 & 1/4\n", "\\end{pmatrix}\n", "$$\n", "\n", "et pour $\\alpha = 0.5$, on a :\n", "$$\n", "M_0^{0.5} = \\begin{pmatrix}\n", "0.125 & 0.625 & 0.125 & 0.125 \\\\\n", "0.125 & 0.125 & 0.375 & 0.375 \\\\\n", "0.292 & 0.292 & 0.125 & 0.292 \\\\\n", "0.25 & 0.25 & 0.25 & 0.25\n", "\\end{pmatrix}\n", "$$\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 7.a.** Expliquer pourquoi cette matrice ainsi définie correspond bien au comportement du \"surfeur aléatoire\" ? Quelle est l'influence du paramètre $\\alpha$ ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Réponse :*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 7.b.** Adapter la fonction `matrice` de la partie précédente pour calculer cette nouvelle matrice. Vérifiez que vous obtenez bien la bonne matrice sur les liens de notre base de données `websites`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def matrice_surfeur_aleatoire(links, alpha=0.1):\n", " # ~~~ implémentez la fonction ~~~" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 7.c.** Vérifiez que vous obtenez la même chose que ci-dessus pour $\\alpha = 1$ et $\\alpha = 0.5$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 7.d.** Recalculez le vecteur calculé à la question 6.a ($(M_0^T)^{100}$), en remplaçant la matrice $M_0$ par celle obtenue avec la fonction de la question *7.b*, avec $\\alpha = 0.8$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 7.e.** Comparez le vecteur obtenu à celui de la question 5.d." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Réponse :*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Classer des Sites Internet\n", "\n", "Finalement, on va faire un dernier changement : au lieu de supposer que l'on part d'un site donné, on suppose que l'on a autant de chance de partir de n'importe quel site.\n", "On remplacera donc le vecteur $v$ des parties précédentes par un vecteur de longueur $n$ (ou $n$ est le nombre de sites), de la forme $v = [1/n, 1/n, \\dots, 1/n]$.\n", "\n", "**Question 8.a.** Calculer le vecteur obtenu en faisant le calcul $(M^T)^K v$ avec ce vecteur $v$, et où $M$ est la matrice de probabilités correspondant à notre base de données `website`, calculée dans la partie précédente avec $\\alpha = 0.8$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ces valeurs sont ce que l'on appelle le PageRank de ces site.\n", "Plus le PageRank d'un site est grand, plus on considère que ce site est important sur internet.\n", "Cela permet notamment de classer les résultats d'une recherche, permettant de renvoyer d'abord les sites les plus importants, puis les autres.\n", "\n", "Bien sûr, tout ça, c'était le début de Google, maintenant iels utilisent aussi des choses plus compliquées... mais cet algorithme a néanmoins été breveté au début des années 2000 par les fondateurs de l'entreprise." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 8.b.** Quel est le classement des sites correspondant aux PageRank de la question 8.a ? Est-ce que cela vous semble pertinent ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Réponse :*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 8.c.** Étudions l'influence du paramètre $\\alpha$. Pour cela, vous ferez varier $\\alpha$ entre $0$ et $1$ avec un pas de $0.1$.\n", "Pour chaque valeur de $\\alpha$, calculez le PageRank de chacun des sites de la même manière qu'à la question 8.a, et tracez l'évolution du PageRank de chacun des sites en fonction de $\\alpha$.\n", "\n", "Affichez le résultat sous la forme d'un graphique (en utilisant `matplotlib.pyplot`) comportant $4$ courbes, chaque courbe représentant le PageRank d'un site en fonction de $\\alpha$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 8.d.** Expliquez pourquoi, pour $\\alpha > 0$, le PageRank permet de quantifier l'importance d'un site sur internet. Quelle est l'influence du choix de $\\alpha$ ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Réponse :*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question 8.e.** Comment pourrait-on construire un moteur de recherche à partir de cette mesure d'importance des pages web ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Réponse :*" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }